package cn.javadog.algorithm.滑动窗口;

import java.util.HashMap;
import java.util.Map;
import java.util.SortedSet;
import java.util.concurrent.ConcurrentSkipListSet;

/**
 * @author yuy
 * @date 2020-11-10 12:33
 *
 * 904. 水果成篮
 * https://leetcode-cn.com/problems/fruit-into-baskets/
 *
 * 在一排树中，第 i 棵树产生 tree[i] 型的水果。
 * 你可以从你选择的任何树开始，然后重复执行以下步骤：
 *
 * 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
 * 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
 * 请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
 *
 * 你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
 *
 * 用这个程序你能收集的水果树的最大总量是多少？
 *
 **/
public class Algorithm904 {

    public static void main(String[] args) {
        System.out.println(totalFruit(new int[]{1,2,1}));//3
        System.out.println(totalFruit(new int[]{0,1,2,2}));//3
        System.out.println(totalFruit(new int[]{1,2,3,2,2}));//4
        System.out.println(totalFruit(new int[]{3,3,3,1,2,1,1,2,3,3,4}));//5
        System.out.println(totalFruit(new int[]{1,1}));//2
        System.out.println(totalFruit(new int[]{1,1,1,1}));//2
    }

    public static int totalFruit(int[] tree) {
        if (tree.length == 1) return 1;
        Map<Integer, Integer> windows = new HashMap<>();
        int[] win = new int[tree.length];
        int leftIdx = 0, rightIdx = 1;
        int categories = 0, sum = 2;
        int ans = 2;

        windows.put(tree[leftIdx], windows.getOrDefault(tree[leftIdx], 0) + 1);
        if (++win[tree[leftIdx]] == 1) {
            categories++;
        }

        if (++win[tree[rightIdx]] == 1) {
            categories++;
        }

        while (true) {
            // 右边滑
            if (categories <= 2) {
                if (categories == 2 || rightIdx == tree.length -1) {
                    ans = Math.max(ans, sum);
                }
                if (rightIdx == tree.length -1) {
                    break;
                }
                if (++win[tree[++rightIdx]] == 1) {
                    categories++;
                }
                sum++;
            }
            // 左边滑
            else {
                if (--win[tree[leftIdx++]] == 0) {
                    categories--;
                }
                sum--;
            }
        }

        return ans;
    }

}
